package com.agile.leetcode.node.isPalindrome;


/**
 * 234. 回文链表
 * 请判断一个链表是否为回文链表。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 * <p>
 * 输入: 1->2->2->1
 * 输出: true
 * 进阶：
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 * @Author:ChenZhangKun
 * @Date: 2021/5/14 9:40
 */
public class IsPalindrome {
    public static void main(String[] args) {
        ListNode node4 = new ListNode(1, null);
        ListNode node3 = new ListNode(2, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        IsPalindrome palindrome = new IsPalindrome();
        System.out.println(palindrome.isPalindrome(node1));


    }

    /**
     * 是否是回文链表
     *
     * @param head
     * @return
     */
    public boolean isPalindrome_1(ListNode head) {
        // 判断
        if (head == null || head.next == null) {
            return true;
        }
        // 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && slow != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 翻转slow
        slow = reserve(slow);
        // 遍历

        while (slow != null) {
            if (slow.val != head.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        // 判断
        if (head == null || head.next == null) {
            return true;
        }
        // 根据快慢指针找到终点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && slow != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时slow是中点
        // 翻转链表
        slow = reserve(slow);
        while (slow != null) {
            if (slow.val != head.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

    private ListNode reserve(ListNode head) {
        if (head.next == null) {
            return head;
        }
        // 递归
        ListNode newHead = reserve(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode() {
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}
